package class71To80;

import java.io.*;
import java.util.Arrays;


// 分组背包问题模板
// https://www.luogu.com.cn/problem/P1757
public class PartitionedKnapsack {

    public static int MAX_N = 1005;

    public static int n, m;

    public static int[][] arr = new int[MAX_N][3];

    public static int[] dp = new int[MAX_N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(System.out);
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            m = (int) in.nval;
            in.nextToken();
            n = (int) in.nval;
            for (int i = 1; i <= n; i++) {
                in.nextToken();
                arr[i][0] = (int) in.nval;
                in.nextToken();
                arr[i][1] = (int) in.nval;
                in.nextToken();
                arr[i][2] = (int) in.nval;
            }
            Arrays.sort(arr, 1, n + 1, (a, b) -> a[2] - b[2]);
            System.out.println(solve1());
        }
        out.flush();
        out.close();
        br.close();
    }

    // 二维动态规划
    private static int solve1() {
        int teams = 1;
        for (int i = 2; i <= n; i++) {
            if (arr[i][2] != arr[i - 1][2]) {
                teams++;
            }
        }
        int[][] dp = new int[teams + 1][m + 1];
        for (int start = 1, end = 2, i = 1; i <= teams; i++) {
            while (end <= n && arr[start][2] == arr[end][2]) {
                end++;
            }
            for (int j = 0; j <= m; j++) {
                dp[i][j] = dp[i - 1][j];
                for (int k = start; k < end; k++) {
                    if (j >= arr[k][0]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - arr[k][0]] + arr[k][1]);
                    }
                }
            }
            start = end++;
        }
        return dp[teams][m];
    }

    // 空间压缩
    private static int solve2() {
        Arrays.fill(dp, 0, m + 1, 0);
        for (int start = 1, end = 2, i = 1; start <= n; i++) {
            while (end <= n && arr[start][2] == arr[end][2]) {
                end++;
            }
            for (int j = m; j >= 0; j--) {
                for (int k = start; k < end; k++) {
                    if (j >= arr[k][0]) {
                        dp[j] = Math.max(dp[j], dp[j - arr[k][0]] + arr[k][1]);
                    }
                }
            }
            start = end++;
        }
        return dp[m];
    }
}
